package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         4,
		Discription: "两个升序数组合并后的中位数",
		Level:       3,
		Labels: map[string]int{
			"二分查找": 1,
			"奇偶性":  1,
		},
	})
}

// 转化为：找数组的第k个数，k为中间位置
//中位数为：第（len1+len2+1）/2个数 和  第（len1+len2+2）/2个数的平均数，从1开始计数
func FindMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	var findKth func(int, int, int) int
	//从nums的start1开始，nums2的start2开始的第k个数
	findKth = func(start1, start2, k int) int {
		//如果其中一个数组没了，就都从另外一个数组取
		if start1 >= len(nums1) {
			return nums2[start2+k-1]
		}

		if start2 >= len(nums2) {
			return nums1[start1+k-1]
		}

		//如果只需要找第一个数，返回更小的那个即可
		if k == 1 {
			if nums1[start1] < nums2[start2] {
				return nums1[start1]
			} else {
				return nums2[start2]
			}
		}

		//两个数组各加k/2个数，比大小后缩小区间
		//注意mid可能越界，越界直接取最后一个数
		mid1 := start1 + k/2 - 1
		if mid1 >= len(nums1) {
			mid1 = len(nums1) - 1
		}
		mid2 := start2 + k/2 - 1
		if mid2 >= len(nums2) {
			mid2 = len(nums2) - 1
		}
		if nums1[mid1] <= nums2[mid2] {
			//缩小区间，减去那些已排除过的区间（用mid-start+1算）
			return findKth(mid1+1, start2, k-mid1+start1-1)
		} else {
			return findKth(start1, mid2+1, k-mid2+start2-1)
		}
	}

	return float64(findKth(0, 0, (len(nums1)+len(nums2)+1)/2)+findKth(0, 0, (len(nums1)+len(nums2)+2)/2)) / float64(2)
}